1. Field of the Invention
The present invention relates to a high-speed semiconductor operation device, and concerns a multiplication circuit suitable for increasing the speed of operation in particular.
2. Description of the Prior Art
As described in Japanese Patent Application Laid Open No. 63-1258, a multiplication circuit which reads a value from a memory device which stores a coefficient and performs multiplication between the value and another input value heretofore has had an independent multiplier and an independent coefficient memory device. A circuit structured by adopting a Booth algorithm to this multiplier is shown in FIG. 2. Generally, a 2's complement, which is often used in digital operation, is used in a parallel multiplier. Considering an 8 bit.times.8 bit multiplication, for instance, the two 8-bit numbers that are expressed as 2's complements (X and Y) can be expressed as Equations (1) and (2). EQU X=-2.sup.7 x.sub.7 +2.sup.6 x.sub.6 +2.sup.5 x.sub.5 + . . . +2.sup.0 x.sub.0 ( 1) EQU Y=-2.sup.7 y.sub.7 +2.sup.6 y.sub.6 +2.sup.5 y.sub.5 + . . . +2.sup.0 y.sub.0 ( 2)
In multiplication between 8 bits in the past, 8 additions were performed as shown in (3). EQU X.times.Y=X.times.(-2.sup.7 y.sub.7)+X.times.(2.sup.6 y.sub.6)+ . . . +X.times.(2.sup.0 y.sub.0) (3)
Meanwhile, a multiplier Y is expressed as follows in a Booth algorithm. EQU Y=2.sup.6 (-2y.sub.7 +y.sub.6 +y.sub.5)+2.sup.4 (-2y.sub.5 +y.sub.4 +y.sub.3)+2.sup.2 (-2y.sub.3 +y.sub.2 +y.sub.1)+2.sup.0 (-2y.sub.1 y.sub.0)(4)
Performing a multiplication by using Equation (4) as shown in the following equation reduces the addition from 8 times to 4 times. EQU X.times.Y=X.times.2.sup.6 ( )+X.times.2.sup.4 ( )+X.times.2.sup.2 ( )+X.times.2.sup.0 ( ) (5)
Figures inside the parentheses in Equation (5) are calculated from 3 bits of y.sub.i+1, y.sub.i and y.sub.i-1 and create Booth codes that are 0, .+-.1 or .+-.2. These Booth codes are used to obtain and sum up four partial products. Since calculation of a partial product only requires shift or inversion, it will not bring about an increase in the scale of a circuit in particular. Compared to an ordinary parallel multiplier which does not use this algorithm, the device using this algorithm seeks to improve the speed of the multiplier by reducing the number of adders in an array from 8 steps to 4 steps by obtaining a partial product for every 2 digits and summing them up.
A coefficient memory 1 where the coefficient shown in FIG. 2 is stored outputs the content of an address that has been designated by an address signal 5 to a Booth encoder 2 of a multiplier. A Booth encoder is a circuit which generates Booth codes 0, .+-.1 or .+-.2 from a binary number which is expressed as a 2's complement in the foregoing explanation of the Booth algorithm. Therefore, the content of a coefficient memory 1 is converted to a Booth code with a Booth encoder 2 and input to a Booth decoder 3. A Booth decoder refers to a circuit which performs multiplication between the Booth code generated from a Booth encoder and an input X and generates a partial product. Accordingly, an output of a multiplier refers to plural partial products which have been output from a Booth decoder that are added up by an adding circuit 4 which is comprised of a half adder and a full adder.
Such a combination of a multiplier and a coefficient memory device is used for an A/D converted digital signal or a signal which corresponds to it, and is used frequently for a digital filter which basically performs an operation with the combination of an adder and a delay element with a sampling period of T to obtain a given output. It has a broad range of application and is used particularly in filters for time sequential signals such as sound and control. For instance, considering a logic circuit which realizes a transfer function such as H (Z)=C.sub.0 +C.sub.1 Z.sup.-1 +C.sub.2 Z.sup.-2 +C.sub.3 Z.sup.-3 +C.sub.4 Z.sup.-4 (Z.sup.-1 is a delay operator) through digital operation and performs filtering of signals, outputs A.sub.-6, A.sub.-5, A.sub.-4, . . . A.sub.0, A.sub.1, A.sub.2 . . . can be expressed as follows when a signal such as X.sub.-6, X.sub.-5, X.sub.-4, . . . X.sub.0, X.sub.1, X.sub.2 . . . is input to this circuit as shown in FIG. 3. EQU A.sub.0 =C.sub.0 X.sub.0 +C.sub.1 X.sub.-1 +C.sub.2 X.sub.-2 +C.sub.3 X.sub.-3 +C.sub.4 X.sub.-4 EQU A.sub.1 =C.sub.0 X.sub.1 +C.sub.1 X.sub.0 +C.sub.2 X.sub.-1 +C.sub.3 X.sub.-2 +C.sub.4 X.sub.-3 EQU A.sub.2 =C.sub.0 X.sub.2 +C.sub.1 X.sub.1 +C.sub.2 X.sub.0 +C.sub.3 X.sub.-1 +C.sub.4 X.sub.-2 EQU A.sub.3 =C.sub.0 X.sub.0 +C.sub.1 X.sub.2 +C.sub.2 X.sub.1 +C.sub.3 X.sub.0 +C.sub.4 X.sub.-1 EQU A.sub.4 =C.sub.0 X.sub.4 +C.sub.1 X.sub.0 +C.sub.2 X.sub.2 +C.sub.3 X.sub.1 +C.sub.4 X.sub.0 ( 6)
The prior art in FIG. 2 performs this operation by using an operation circuit which is capable of performing an operation in fractions an input cycle time. In other words, when X.sub.0 is input, it successively performs five multiplications C.sub.0 X.sub.0, C.sub.1 X.sub.0, C.sub.2 X.sub.0, C.sub.3 X.sub.0, C.sub.4 X.sub.0 with one multiplier. When X.sub.1 is input next, five multiplications of C.sub.0 X.sub.1, C.sub.1 X.sub.1, C.sub.2 X.sub.1, C.sub.3 X.sub.1, C.sub.4 X.sub.1 are successively performed. Thus, it is necessary to perform multiplications of C.sub.0 X, C.sub.1 X, C.sub.2 X, C.sub.3 X, C.sub.4 X successively and repeatedly with multipliers of the prior art. The filter output A.sub.0, A.sub.1, . . . is obtained by summing the products which were obtained in the above manner as shown in Equation (6) by using the adder 7 and delay circuit 8 shown in FIG. 3. In FIG. 3, coefficients C.sub.0, C.sub.1, C.sub.2 and C.sub.3 are output repeatedly from coefficient memory 1 when X.sub.0, X.sub.1, X.sub.2, . . . are input as an X input to a Booth decoder 3 and converted into Booth codes B.sub.0, B.sub.1, b.sub.2 and b.sub.3 by a Booth encoder 2. Here, as shown in the timing chart in FIG. 4, the input X.sub. 0 is multiplied by the coefficients C.sub.0, C.sub.1, C.sub.2 and C.sub.3, with the same operation performed for X.sub.1 and X.sub.2.
When the above prior art is used, Booth codes corresponding to coefficients C.sub.0, C.sub.1, C.sub.2 and C.sub.3 will appear repeatedly at the output terminal of a Booth encoder 2. A Booth encoder 2 will be repeating the operation of converting coefficients C.sub.0, C.sub.1, C.sub.2 and C.sub.3 into Booth codes. However, rewriting of a coefficient is normally nil or extremely rare after the system algorithm is determined. Accordingly, conversion the coefficient to a Booth code by Booth encoder 2 is extremely inefficient as the same operation is merely repeated until the coefficient is changed.
In addition, few examinations concerning the time of processing required for encoding of a coefficient have been conducted up to now. For this reason, a simulation was performed on a circuit which has a structure similar to a multiplier using a conventional 8 bit.times.8 bit second-order Booth algorithm, revealing that the time of processing required for encoding accounts for approximately 15% of the time required for an entire multiplication of the multiplier. Moreover, use of a Booth algorithm of a higher order will be accompanied by a longer processing time for encoding. Therefore, it was revealed that, in a multiplier using a higher order Booth algorithm, the percentage of processing time required for encoding in the entire multiplication increases further. Furthermore, when a digital filter is structured by using the foregoing multiplication circuit, there was a problem of limitations in a number of filter taps and operation speed due to insufficient operation speed of the multiplication circuit.